#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>

#define STDIN
//#define DEBUG

int M, N, K, T;
int leftK;
int totalPeanuts;

typedef struct tagPeanut
{
    int num;
    short int x;
    short int y;
} Peanut;

Peanut peanuts[2500];
int np = 0;

int compare(void* a, void* b)
{
    return -(((Peanut*)a)->num - ((Peanut*)b)->num);
}

int can_pick(int sx, int sy, int dx, int dy, int left_time)
{
    if (abs(dx - sx) + abs(dy - sy) + 1 + dy <= left_time)
        return 1;
    else
        return 0;
}

void process()
{
    int i;

    qsort(peanuts, np, sizeof(Peanut), compare);

#ifdef DEBUG
    for (i = 0; i < np; ++i)
    printf("%d %d %d\n", peanuts[i].num, peanuts[i].x, peanuts[i].y);
#endif

    totalPeanuts = 0;
    leftK = K;
    int sx =peanuts[0].x, sy = 0;
    int dx = peanuts[0].x, dy = peanuts[0].y;
    for (i = 0; i < np; ++i)
    {
        dx = peanuts[i].x, dy = peanuts[i].y;
        if (can_pick(sx, sy, dx, dy, leftK))
        {
#ifdef DEBUG
            printf("sx: %d sy: %d\n", sx, sy);
#endif
            totalPeanuts += peanuts[i].num; 
            leftK -= (abs(dx - sx) + abs(dy - sy) + 1);
            sx = dx;
            sy = dy;
#ifdef DEBUG
            printf("x: %d y: %d 能摘, totalPeanuts: %d leftK: %d\n", dx, dy, totalPeanuts, leftK);
#endif
        }
        else
        {
            break;
        }
    }
    printf("%d\n", totalPeanuts);
}

int main()
{
#ifdef  STDIN
    freopen("bin/1928.in", "r", stdin);
#endif

    scanf("%d", &T);
    int t, i, j, tmp;
    for (t = 0; t < T; ++t)
    {
        scanf("%d %d %d", &M, &N, &K);
        memset(peanuts, 0, sizeof(peanuts));
        np = 0;
        for (j = 1; j <= M; ++j)
        {
            for (i = 1; i <= N; ++i)
            {
                scanf("%d", &tmp);
                if (tmp != 0)
                {
                    peanuts[np].num = tmp;
                    peanuts[np].x = i;
                    peanuts[np].y = j;
                    np++;
                }
            }
        }
        process();

    }


    return 0;

    
}
